package J3_10;

import java.util.*;

public class test {
    //给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
    //
    //子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
    //子序列
    //。
    public static int lengthOfLIS(int[] nums) {

        if (nums.length == 0) {
            return 0;
        }

        ArrayList<Integer> list = new ArrayList<>();

        list.add(nums[0]);

        for(int i = 1;i < nums.length;i++) {
            int min = list.get(0);
            int max = list.get(list.size()-1);
            int n = nums[i];
            if (n < min) {
                list.set(0,n);
            } else if (n > max){
                list.add(n);
            } else {
                int left = 0;
                int right = list.size() - 1;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (list.get(mid) < n) {
                        left = mid + 1;
                    }else if (list.get(mid) > n){
                        right = mid - 1;
                    } else {
                        left = mid;
                        break;
                    }
                }
                list.set(left,n);
            }
        }
        return list.size();
    }



    //给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
    //
    //返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        for (String str: words) {
                map.put(str,map.getOrDefault(str,0)+1);
        }
        List<String> list = new LinkedList<>();
        for (Map.Entry<String,Integer> entry : map.entrySet() ) {
            list.add(entry.getKey());
        }

        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });

        return list.subList(0,k);
    }


    //你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
    //
    //写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
    //
    //猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
    //有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
    //给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
    //
    //提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
    //
    //请注意秘密数字和朋友猜测的数字都可能含有重复数字。
    public static String getHint(String secret, String guess) {
        int len = secret.length();
        int a = 0;
        int b = 0;
        boolean[] sec = new boolean[len];
        boolean[] gue = new boolean[len];
        for (int i = 0; i < len; i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                sec[i] = true;
                gue[i] = true;
                a++;
            }
        }
        for (int i = 0; i < len; i++) {
            if (sec[i]) {
                continue;
            }
            int index = guess.indexOf(secret.charAt(i));
            while (true) {
                if (index == -1) {
                    break;
                }
                if (gue[index]) {
                    index = guess.indexOf(secret.charAt(i),index+1);
                    continue;
                } else {
                    gue[index] = true;
                    b++;
                    break;
                }
            }
        }
        return a+"A"+b+"B";
    }

    public static void main(String[] args) {
        String a = "1123";
        String b = "0111";
        System.out.println(getHint(a, b));
    }
}
